package code.commonAlgorithm;

import utils.TreeNode;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/12/30
 */
public class TreeTraversal {

    /* 非递归的前序遍历 */
    static public List<Integer> firstOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
    }

    /* 非递归的中序遍历 */
    static public List<Integer> inOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        return list;
    }

    static public List<Integer> inOrderMorris(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode node = root, prev = null;
        while (node != null) {
            if (node.left == null) {
                list.add(node.val);
                node = node.right;
                continue;
            }
            prev = node.left;
            while (prev.right != null && prev.right != node) {
                prev = prev.right;
            }
            if (prev.right == null) {
                prev.right = node;
                node = node.left;
            } else {
                prev.right = null;
                list.add(node.val);
                node = node.right;
            }
        }
        return list;
    }

    /* 非递归的后序遍历 */
    static public List<Integer> postOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        TreeNode prev = null;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                prev = node;
                node = node.left;
            }
            node = stack.pop();
            if (node.right == null || node.right == prev) {
                // 右面遍历了
                list.add(node.val);
                prev = node;
                node = null;
            } else {
                // 右面没遍历
                stack.push(node);
                node = node.right;
            }
        }
        return list;
    }
}
